package collection;

import java.util.Objects;

/**
 * 自定义LinkedList类，用于存储任意类型的元素
 * 使用双向链表实现，支持快速插入和删除操作
 * @param <T> 元素类型
 */
public class MyLinkedList<T> {
    /**
     * 内部节点类，用于表示链表中的一个节点
     * 包含节点值以及前驱和后继节点的引用
     * @param <T> 元素类型
     */
    static private class Node<T> {
        public T val;
        public Node<T> prev;
        public Node<T> next;

        public Node(T val) {
            this.val = val;
        }

        public Node() {
        }
    }

    private int size;
    private Node<T> head;
    private Node<T> tail;

    /**
     * 构造一个空的LinkedList
     */
    public MyLinkedList() {
        size = 0;
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取链表中元素的数量
     * @return 元素数量
     */
    public int size() {
        return this.size;
    }

    /**
     * 判断链表是否为空
     * @return 如果链表为空，则返回true，否则返回false
     */
    public boolean isEmpty() {
        return head.next == tail;
    }

    /**
     * 检查链表中是否包含指定元素
     * @param o 要检查的元素
     * @return 如果链表中包含指定元素，则返回true，否则返回false
     */
    public boolean contains(T o) {
        Node<T> cur = head.next;
        while (cur != tail) {
            if (Objects.equals(o, cur.val)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 在链表末尾添加一个元素
     * @param val 要添加的元素
     */
    public void add(T val) {
        add(size(), val);
    }

    /**
     * 从链表中移除指定元素
     * @param o 要移除的元素
     * @return 如果链表中包含指定元素并且成功移除，则返回true，否则返回false
     */
    public boolean remove(Object o) {
        Node<T> cur = head.next;
        Node<T> prev = head;
        while (cur != tail) {
            if (Objects.equals(o, cur.val)) {
                if (cur == tail.prev) {
                    tail.prev = prev;
                } else {
                    prev.next = cur.next;
                    cur.next.prev = prev;
                }
                cur.next = null;
                cur.prev = null;
                size--;
                return true;
            }
            prev = cur;
            cur = cur.next;
        }
        return false;
    }

    /**
     * 清空链表中的所有元素
     */
    public void clear() {
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    /**
     * 获取指定位置的元素
     * @param index 元素索引
     * @return 该位置的元素
     * @throws IndexOutOfBoundsException 如果索引超出链表长度，则抛出此异常
     */
    public T get(int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException("越界");
        }
        Node<T> cur = head.next;
        while (index-- > 0) {
            cur = cur.next;
        }
        return cur.val;
    }

    /**
     * 设置指定位置的元素值
     * @param index 元素索引
     * @param element 新的元素值
     * @return 旧的元素值
     * @throws IndexOutOfBoundsException 如果索引超出链表长度，则抛出此异常
     */
    public T set(int index, T element) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException("越界");
        }
        Node<T> cur = head.next;
        while (index-- > 0) {
            cur = cur.next;
        }
        T val = cur.val;
        cur.val = element;
        return val;
    }

    /**
     * 在指定位置插入一个元素
     * @param index 插入位置
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException 如果索引超出链表长度，则抛出此异常
     */
    public void add(int index, T element) {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException("下标出界");
        }
        Node<T> prev = head;
        while (index-- > 0) {
            prev = prev.next;
        }
        Node<T> node = new Node<>(element);
        Node<T> next = prev.next;
        node.next = next;
        node.prev = prev;
        prev.next = node;
        next.prev = node;
        if (next == tail) {
            tail.prev = node;
        }
        size++;
    }

    /**
     * 移除指定位置的元素
     * @param index 元素索引
     * @return 被移除的元素
     * @throws IndexOutOfBoundsException 如果索引超出链表长度，则抛出此异常
     */
    public T remove(int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException("下标出界");
        }
        Node<T> prev = head;
        while (index-- > 0) {
            prev = prev.next;
        }

        Node<T> next = prev.next;
        prev.next = next.next;
        next.next.prev = prev;
        T val = next.val;
        next.next = null;
        next.prev = null;
        size--;

        return val;
    }
}
